(Problem) 003 Largest prime factor

Project Euler

• 공식 홈페이지 - projecteuler.net
• 한글 번역 - projecteuler @kr
• (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Problem list

• No 3 : Largest prime factor
  • HackerRank : Project Euler #3: Largest prime factor

Largest prime factor

참고 - stackoverflow.com

problem <번역>

solution

Simple Code

소수(prime number)룰 구하는 방법으로 흔히 2가지 알고리즘을 사용한다
밀러-라빈 소수 판별법 (Miller-Rabin Primality Test) 과
에라토스테네스의 체 (Sieve of Eratosthenes) 이다.
문제는 소인수(prime factor) 즉, 소수이면서 약수인 수 중 가장 큰 값을 찾는 것이다.
아래는 밀러-라빈 소수 판별법 알고리즘을 사용한 풀이이다.

003_Largest_prime_factor.py

def largest_prime_factor(N):
  num = 2
  prime = []

  while N != 1:
      if N % num:
          num += 1
      else:
          N = N // num
          prime.append(num)

  return prime[-1]


print(largest_prime_factor(600851475143))  

---

HackerRank

에라토스테네스의 체 알고리즘을 사용한 풀이는 다음과 같다

003_for_HacerRank.py

from math import sqrt


def largest_prime_factor(N):
  prime = []

  while N % 2 == 0:
      prime.append(2)
      N //= 2
  for i in range(3, int(sqrt(N))+1, 2):
      while N % i == 0:
          prime.append(i)
          N //= i

  if N > 2:
      prime.append(N)

  return max(prime)


if __name__ == '__main__':
  for _ in range(int(input())):
      N = int(input())
      print(largest_prime_factor(N)) 

파이썬에는 사용자의 편의를 위해 sympy 모듈 에서 primefactors를 제공한다.
(소수를 구하고 싶다면 primerange(1, N)을 사용하면 된다. 아래는 100까지의 소수와 소인수를 구한 예제)

003_sympy_primefactor.py

from sympy import primerange
from sympy import primefactors

print(*primerange(1, 100))  # 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
print(primefactors(100))    # [2, 5] 

에라토스테네스의 체 보다 밀러-라빈 소수 판별법이 간단하고 수행 속도도 더 빠르다
sympy 모듈의 함수들도 잘 기억하고 있자!